import itertools
from collections import deque

'''
17.2 Give all the connected subgraphs of the graph `0-1 0-2 0-3 1-3 2-3`.
'''
def to_canonical_edge(u, v):
    """将无向边标准化，确保 (u, v) 和 (v, u) 被视为同一条边"""
    return tuple(sorted((u, v)))

def is_connected(vertices_sub, edges_sub):
    """
    检查给定顶点子集和边子集构成的图是否连通。
    vertices_sub: frozenset of vertices
    edges_sub: frozenset of canonical edges
    """
    if not vertices_sub:
        return True # 空图在某些语境下可视为连通，但本题中我们只考虑非空图

    if len(vertices_sub) == 1:
        # 单个顶点（无论是否有边，但通常单顶点子图无边）总是连通的
        return True

    if not edges_sub:
        # 如果有多个顶点但没有边，则不连通
        return False

    # 构建子图的邻接表
    adj = {v: set() for v in vertices_sub}
    for u, v in edges_sub:
        # 确保边连接的顶点都在当前子图的顶点集中
        if u in vertices_sub and v in vertices_sub:
            adj[u].add(v)
            adj[v].add(u)
        else:
            # 理论上，根据子图的构造方式，这里的else分支不应该被触发
            # 因为edges_sub的边都是从vertices_sub中提取端点的
            pass

    # 执行 BFS/DFS 来检查连通性
    start_node = next(iter(vertices_sub)) # 选取任意一个顶点作为起点

    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        current_node = queue.popleft()
        for neighbor in adj[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    # 如果访问过的顶点数量等于子图的顶点总数，则说明图是连通的
    return len(visited) == len(vertices_sub)

# --- 定义原图 ---
original_vertices = frozenset({0, 1, 2, 3})
# 将边标准化，确保顺序一致性
original_edges = frozenset([
    to_canonical_edge(0, 1),
    to_canonical_edge(0, 2),
    to_canonical_edge(0, 3),
    to_canonical_edge(1, 3),
    to_canonical_edge(2, 3)
])

connected_subgraphs = set()

# --- 1. 添加单顶点连通子图 (不含边) ---
# 这对应于从原图的5条边中选择0条边，但顶点集是单个顶点
for v in original_vertices:
    connected_subgraphs.add((frozenset({v}), frozenset()))

# --- 2. 遍历所有可能的边子集 (从 1 条边到总边数) ---
for num_edges_in_subset in range(1, len(original_edges) + 1):
    # itertools.combinations 生成所有可能的边子集
    for edge_subset_tuple in itertools.combinations(original_edges, num_edges_in_subset):
        edge_subset = frozenset(edge_subset_tuple) # 将元组转换为frozenset以便哈希

        # 确定由当前边子集包含的顶点集
        current_vertices_sub = set()
        for u, v in edge_subset:
            current_vertices_sub.add(u)
            current_vertices_sub.add(v)

        # 检查这个子图是否连通
        if is_connected(frozenset(current_vertices_sub), edge_subset):
            connected_subgraphs.add((frozenset(current_vertices_sub), edge_subset))

# --- 打印结果 ---
print(f"根据您的分析，通过Python程序模拟得出的连通子图总数为: {len(connected_subgraphs)}")

# # 可选：打印每个连通子图的详细信息，用于验证
# print("\n所有连通子图 (V, E):")
# # 为了更好的可读性，对结果进行排序
# sorted_subgraphs = sorted(list(connected_subgraphs),
#                           key=lambda x: (len(x[0]), len(x[1]), sorted(list(x[0]))))
# for i, (v_sub, e_sub) in enumerate(sorted_subgraphs):
#     edges_str = ', '.join([f"{u}-{v}" for u,v in sorted(list(e_sub))])
#     print(f"  {i+1}: V={sorted(list(v_sub))}, E={{ {edges_str} }}")